//前k个高频词汇

class Solution {
public:
        struct Compare
        {
            bool operator()(const pair<int,string>& p1,const pair<int,string>& p2)
            {
                return p1.first>p2.first ||(p1.first == p2.first && p1.second < p2.second);
            }
        };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> dict;
        //首先进行统计
        for(auto& e: words)
        {
            dict[e]++;
        }
        
        vector<pair<int,string>> v;
        for(auto& kv:dict)
        {
            v.push_back(make_pair(kv.second,kv.first));
        }
        //然后进行排序
        //sort这里的仿函数主要是需要可以自由访问的迭代器区间，才能使用默认的less和greater
        sort(v.begin(),v.end(),Compare());  //这里注意不能直接使用greater根less，因为这里
                                                  //比较的是pair()类型的数据,这里需要重写仿函数
        vector<string> ret;
        for(int i=0;i<k;i++)
        {
            ret.push_back(v[i].second);
        }

        return ret;
    }
};


//找公共的数据集，并去重
// class Solution {
// public:
//     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//         map<int,int> andnum;
//         for(auto& e:nums1)
//         {
//             andnum[e]++;
//         }
//         set<int> s;
//         for(auto& e:nums2)
//         {
//             auto it = andnum.find(e);
//             if(it!=andnum.end())
//             {
                
//                 s.insert(e);
//             }
//         }
//         vector<int> v;
//         for(auto& x:s)
//         {
//             v.push_back(x);
//         }
        
//         return v;
//     }
// };

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //排序＋去重
        set<int> s1(nums1.begin(),nums1.end());
        set<int> s2(nums2.begin(),nums2.end());
        auto it1 =s1.begin();
        auto it2 =s2.begin();
        vector<int> v;
        while(it1 !=s1.end() && it2 != s2.end())
        {
            if(*it1 == *it2)
            {
                v.push_back(*it1);
                ++it1;
                ++it2;
            }
            else if(*it1<*it2)
            {
                ++it1;
            }
            else
            {
                ++it2;
            }
        }
        return v;
    }
};

